package org.example.algorithm.dp;

import java.math.BigInteger;
import java.util.Arrays;

public class LargestNumberSolution {
    BigInteger MIN_VALUE = new BigInteger(String.valueOf(Integer.MIN_VALUE));
    BigInteger ZERO = new BigInteger("0");

    public static void main(String[] args) {
        int[] cost = {4,3,2,5,6,7,2,5,5};
        int target = 9;
        LargestNumberSolution solution = new LargestNumberSolution();
        String res = solution.largestNumber(cost, target);
        System.out.println(res);
    }

    public String largestNumber(int[] cost, int target) {
        if (cost == null || cost.length == 0) {
            return "0";
        }
        BigInteger[] dp = new BigInteger[target+1];
        Arrays.fill(dp, MIN_VALUE);
        dp[0] = ZERO;
        for (int i=0;i<=target;i++) {
            for (int j=0;j<cost.length;j++) {
                int numCost = cost[j];
                if (numCost <= i && !dp[i-numCost].equals(MIN_VALUE)) {
                    dp[i] = calMaxNum(dp[i], dp[i-numCost], j+1);
                }
            }
        }
        return dp[target].equals(MIN_VALUE) ? "0" : String.valueOf(dp[target]);
    }

    private BigInteger calMaxNum(BigInteger base, BigInteger l, int num) {
        BigInteger newNum;
        if (!l.equals(ZERO)) {
            newNum = l.multiply(new BigInteger("10")).add(new BigInteger(String.valueOf(num)));
        } else {
            newNum = new BigInteger(String.valueOf(num));
        }
        return newNum.compareTo(base) >=0 ? newNum : base;
    }

    //dp[i]代表target=i时组成的最大数字
    public String largestNumber2(int[] cost, int target) {
        if (cost == null || cost.length == 0) {
            return "0";
        }
        String[] dp = new String[target+1];
        Arrays.fill(dp, "x");
        dp[0] = "0";
        for (int i=0;i<=target;i++) {
            for (int j=0;j<cost.length;j++) {
                int numCost = cost[j];
                if (numCost <= i && !dp[i-numCost].equals("x")) {
                    dp[i] = calMaxNum2(dp[i], dp[i-numCost], j+1);
                }
            }
        }
        return dp[target].equals("x") ? "0" : dp[target];
    }

    private String calMaxNum2(String base, String s, int num) {
        StringBuilder sb = new StringBuilder();
        sb.append(num);
        if (!s.equals("0")) {
            sb.append(s);
        }
        String newStr = sb.toString();
        if (base.equals("x")) {
            return newStr;
        }
        if (newStr.length() > base.length()) {
            return newStr;
        } else if (newStr.length() < base.length()) {
            return base;
        } else {
            return base.compareTo(newStr) > 0 ? base : newStr;
        }
    }
}
